On the Computation of 3D Visibility Skeletons
Identifieur interne : 003049 ( Main/Exploration ); précédent : 003048; suivant : 003050On the Computation of 3D Visibility Skeletons
Auteurs : Sylvain Lazard [France] ; Christophe Weibel [Canada] ; Sue Whitesides [Canada] ; Linqiao Zhang [Canada]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is empirically about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. The running time complexity, which we analyze in terms of output size, is efficient. We also prove that the subset is minimal in the sense that the complexity bound ceases to hold if the subset is restricted further.
Url:
DOI: 10.1007/978-3-642-14031-0_50
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003C11
- to stream Istex, to step Curation: 003B67
- to stream Istex, to step Checkpoint: 000811
- to stream Main, to step Merge: 003106
- to stream Main, to step Curation: 003049
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Computation of 3D Visibility Skeletons</title><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></author><author><name sortKey="Weibel, Christophe" sort="Weibel, Christophe" uniqKey="Weibel C" first="Christophe" last="Weibel">Christophe Weibel</name></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name></author><author><name sortKey="Zhang, Linqiao" sort="Zhang, Linqiao" uniqKey="Zhang L" first="Linqiao" last="Zhang">Linqiao Zhang</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:FAA563E76AEAFB72503147CC62A84D38B2E4ACAD</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-14031-0_50</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-Q4W78N4F-B/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003C11</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003C11</idno><idno type="wicri:Area/Istex/Curation">003B67</idno><idno type="wicri:Area/Istex/Checkpoint">000811</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000811</idno><idno type="wicri:doubleKey">0302-9743:2010:Lazard S:on:the:computation</idno><idno type="wicri:Area/Main/Merge">003106</idno><idno type="wicri:Area/Main/Curation">003049</idno><idno type="wicri:Area/Main/Exploration">003049</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Computation of 3D Visibility Skeletons</title><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>INRIA Nancy Grand Est, LORIA, Nancy</wicri:regionArea><placeName><region type="region">Grand Est</region><region type="old region">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Weibel, Christophe" sort="Weibel, Christophe" uniqKey="Weibel C" first="Christophe" last="Weibel">Christophe Weibel</name><affiliation wicri:level="4"><country xml:lang="fr">Canada</country><wicri:regionArea>Math Department, McGill University, H3A 2K6, Montreal, QC</wicri:regionArea><orgName type="university">Université McGill</orgName><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Canada</country></affiliation></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><affiliation wicri:level="1"><country xml:lang="fr">Canada</country><wicri:regionArea>Department of Computer Science, University of Victoria, V8W 3P6, B. C.</wicri:regionArea><wicri:noRegion>B. C.</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Canada</country></affiliation></author><author><name sortKey="Zhang, Linqiao" sort="Zhang, Linqiao" uniqKey="Zhang L" first="Linqiao" last="Zhang">Linqiao Zhang</name><affiliation wicri:level="4"><country xml:lang="fr">Canada</country><wicri:regionArea>School of Computer Science, McGill University, H3A 2A7, Montreal, QC</wicri:regionArea><orgName type="university">Université McGill</orgName><placeName><settlement type="city">Montréal</settlement><region type="state">Québec</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Canada</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The 3D visibility skeleton is a data structure that encodes the global visibility information of a set of 3D objects. While it is useful in answering global visibility queries, its large size often limits its practical use. In this paper, we address this issue by proposing a subset of the visibility skeleton, which is empirically about 25% to 50% of the whole set. We show that the rest of the data structure can be recovered from the subset as needed, partially or completely. The running time complexity, which we analyze in terms of output size, is efficient. We also prove that the subset is minimal in the sense that the complexity bound ceases to hold if the subset is restricted further.</div></front></TEI><affiliations><list><country><li>Canada</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Québec</li></region><settlement><li>Montréal</li><li>Nancy</li></settlement><orgName><li>Université McGill</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></region><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name></country><country name="Canada"><region name="Québec"><name sortKey="Weibel, Christophe" sort="Weibel, Christophe" uniqKey="Weibel C" first="Christophe" last="Weibel">Christophe Weibel</name></region><name sortKey="Weibel, Christophe" sort="Weibel, Christophe" uniqKey="Weibel C" first="Christophe" last="Weibel">Christophe Weibel</name><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><name sortKey="Zhang, Linqiao" sort="Zhang, Linqiao" uniqKey="Zhang L" first="Linqiao" last="Zhang">Linqiao Zhang</name><name sortKey="Zhang, Linqiao" sort="Zhang, Linqiao" uniqKey="Zhang L" first="Linqiao" last="Zhang">Linqiao Zhang</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003049 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003049 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:FAA563E76AEAFB72503147CC62A84D38B2E4ACAD
|texte= On the Computation of 3D Visibility Skeletons
}}
| This area was generated with Dilib version V0.6.33. |  |